home *** CD-ROM | disk | FTP | other *** search
/ The Atari Compendium / The Atari Compendium (Toad Computers) (1994).iso / files / umich / utils / sortsrc.arc / sortcomp.c < prev    next >
C/C++ Source or Header  |  1989-03-06  |  22KB  |  719 lines
  1. /******************************************************************************
  2.  *                                                                            *
  3.  *   sortcomp.c  version 1.0 of  1 Januari 1989    (C) L.J.M. de Wit 1989     *
  4.  *                                                                            *
  5.  * This software may be used and distributed freely if not used commercially  *
  6.  * and the originator (me) is mentioned in the source (just leave this 9 line *
  7.  * header intact).                                                            *
  8.  *                                                                            *
  9.  ******************************************************************************
  10.  *
  11.  * sortcomp.c: comparision functions
  12.  *
  13.  * These functions contain the numeric comparision functions c_n and its
  14.  * reverse, c_nr. The other 48 comparision functions are formed by combining
  15.  * the following properties (take note of the Capitals):
  16.  *  a) either Dictionary, Ignore non-printables or Any other        (3)
  17.  *  b) ignore leading Blanks, versus not ignoring them              (2)
  18.  *  c) Fold upper case to lower, versus not folding                 (2)
  19.  *  d) Reverse the result of the comparision, versus not reversing  (2)
  20.  *  e) Unbounded (bounded only by '\0'), versus upper limit bound   (2)
  21.  *
  22.  * Since comparing is done a lot it is important for the compare functions
  23.  * to be fast. As for using the 48 functions as it stands the following
  24.  * arguments are used:
  25.  * One could have combined functions and used flags to discern between options.
  26.  * This would however involve passing more parameters to the function (the
  27.  * flags) and would require (perhaps a lot of) unwanted testing inside the
  28.  * function.
  29.  * Several functions call one of the other functions. This has been done in
  30.  * such a way that duplication of code is mostly prevented, but still this call
  31.  * is limited to only one (both in number and in level).
  32.  * The numerical compare could have been done by a simple atoi(), but the
  33.  * c_n function does the comparision inline, and stops comparing when the
  34.  * bigger one has been found (while atoi needs to do calculation ala
  35.  * 10 * num + digit, and will use all digits).
  36.  */
  37.  
  38. #include <stdio.h>
  39. #include <ctype.h>
  40. #include "sortmain.h"
  41. #include "sortcomp.h"
  42.  
  43. #define SKIPSPACE(bs,bt) while (wspace(*(bs))) (bs)++; while (wspace(*(bt))) (bt)++
  44.  
  45. #define NCHARS  256
  46. #define NORM 0x1
  47. #define DICT 0x2
  48. #define isnorm(c)   (stype[(c)]&NORM)
  49. #define isdict(c)   (stype[(c)]&DICT)
  50.  
  51. #undef  isdigit
  52. #define isdigit(c) ((c) >= '0' && (c) <= '9')
  53.  
  54. static char fold[NCHARS];                       /* For lcase conversion     */
  55.  
  56. static char stype[NCHARS];                      /* For table lookup         */
  57.  
  58. void initlookup()                               /* Initialize lookup tables */
  59. {
  60.     register int i;
  61.  
  62.     for (i = 0; i < NCHARS; i++) {
  63.         fold[i] = isupper(i) ? tolower(i) : i;  /* Init lcase convert array */
  64.         stype[i] = 0;                           /* Not really needed ...    */
  65.         if (i >= 040 && i <= 0176) {            /* Ascii non-control        */
  66.             stype[i] |= NORM;
  67.         }
  68.         if (wspace(i) || isalnum(i)) {          /* Whitespace & alphanum    */
  69.             stype[i] |= DICT;
  70.         }
  71.     }
  72. }
  73.  
  74. int c_nr(bs,bt,es,et)                           /* Reversed Numeric         */
  75. char *bs, *bt;
  76. char *es, *et;
  77. {
  78.     return c_n(bt,bs,et,es);
  79. }
  80.  
  81. int c_n(bs,bt,es,et)                            /* Numeric compare          */
  82. register char *bs, *bt;
  83. char *es, *et;
  84. {
  85.     register int rev, mini;
  86.  
  87.     SKIPSPACE(bs,bt);
  88.     if (*bs == '-') {
  89.         if (*bt == '-') {                       /* Two negatives: reverse   */
  90.             rev = -1;
  91.             bs++;
  92.             bt++;
  93.         } else {                                /* bt will be the larger one*/
  94.             return -1;
  95.         }
  96.     } else {
  97.         if (*bt == '-') {                       /* bs will be the larger one*/
  98.             return 1;
  99.         } else {
  100.             rev = 1;                            /* Both positive            */
  101.         }
  102.     }
  103.  
  104.     while (*bs == *bt && isdigit(*bt)) {        /* Compare & skip eq. digits*/
  105.         bs++; bt++;
  106.     }
  107.  
  108.     if (!isdigit(*bs)) {
  109.         if (!isdigit(*bt)) {
  110.             if (*bs == '.' && *bt == '.') {     /* Decimal point            */
  111.                 while (*++bs == *++bt && isdigit(*bt)) ;
  112.                 while (*bs == '0') bs++;        /* Skip possibly trailing   */
  113.                 while (*bt == '0') bt++;        /*     zeroes               */
  114.                 if (!isdigit(*bs)) {
  115.                     if (!isdigit(*bt)) {
  116.                         return 0;               /* Tails also equal         */
  117.                     }
  118.                     return -rev;                /* bt has more digits       */
  119.                 }
  120.                 if (!isdigit(*bt)) {
  121.                     return rev;                 /* bs has more digits       */
  122.                 }
  123.                 return (rev == 1)               /* Current digit decides    */
  124.                        ? (*bs - *bt) : (*bt - *bs);
  125.             } else {
  126.                 return 0;                       /* Equal numeric strings    */
  127.             }
  128.         }
  129.         return -rev;                            /* bt has more digits       */
  130.     }
  131.     if (!isdigit(*bt)) {
  132.         return rev;                             /* bs has more digits       */
  133.     }
  134.     mini = (rev == 1)                           /* Current digit decides:   */
  135.            ? (*bs - *bt) : (*bt - *bs);         /* Difference into mini     */
  136.     do {
  137.         bs++;
  138.         bt++;
  139.     } while (isdigit(*bs) && isdigit(*bt));     /* Skip any more digits     */
  140.  
  141.     if (!isdigit(*bs)) {
  142.         if (!isdigit(*bt)) {                    /* Strings equally long:    */
  143.             return mini;                        /* then mini decides        */
  144.         }
  145.         return -rev;                            /* bt has more digits       */
  146.     }
  147.     return rev;                                 /* bs has more digits       */
  148. }
  149.  
  150. int c_df(bs,bt,es,et)                           /* Dictionary/Fold          */
  151. register char *bs, *bt;                         /* Strings to compare       */
  152. register char *es, *et;
  153. {
  154.     --bs;   --bt;   --es;   --et;
  155.     for ( ; bs < es && bt < et; ) {
  156.         if (fold[*++bs] != fold[*++bt]) {       /* Increment & compare      */
  157.             if (isdict(*bs)) {
  158.                 if (isdict(*bt)) {
  159.                     return fold[*bs] - fold[*bt];
  160.                 } else {
  161.                     --bs;                       /* Effectively skip *bt     */
  162.                 }
  163.             } else if (isdict(*bt)) {
  164.                 --bt;                           /* Effectively skip *bs     */
  165.             }                                   /* (else: skip both)        */
  166.         }
  167.     }
  168.     for ( ; bs < es; ) {                        /* Skip any more            */
  169.         if (isdict(*++bs)) {                    /* non-dict chars in bs     */
  170.             --bs;
  171.             break;
  172.         }
  173.     }
  174.     for ( ; bt < et; ) {                        /* Skip any more            */
  175.         if (isdict(*++bt)) {                    /* non-dict chars in bt     */
  176.             --bt;
  177.             break;
  178.         }
  179.     }
  180.  
  181.     return (et - bt) - (es - bs);
  182. }
  183.  
  184. int c_d(bs,bt,es,et)                            /* Dictionary order         */
  185. register char *bs, *bt;
  186. register char *es, *et;
  187. {
  188.     --bs;   --bt;   --es;   --et;
  189.     for ( ; bs < es && bt < et; ) {
  190.         if (*++bs != *++bt) {                   /* Increment & compare      */
  191.             if (isdict(*bs)) {
  192.                 if (isdict(*bt)) {
  193.                     return fold[*bs] - fold[*bt];
  194.                 } else {
  195.                     --bs;                       /* Effectively skip *bt     */
  196.                 }
  197.             } else if (isdict(*bt)) {
  198.                 --bt;                           /* Effectively skip *bs     */
  199.             }                                   /* (else: skip both)        */
  200.         }
  201.     }
  202.     for ( ; bs < es; ) {                        /* Skip any more            */
  203.         if (isdict(*++bs)) {                    /* non-dict chars in bs     */
  204.